Revenues of Search Engine Advertisement Providers (“Providers”) are determined by the number of user visits (clicks or viewings) received by paid advertisements, and/or by per-visit-amounts (Pay-Per-Visit, or PPV) the Advertiser pays to the provider. The business model is well described in Mordkovich et al, Pay-per-Click Search Engine Marketing Handbook(2005). More specifically, typical advertisement contracts between Advertisers and Providers specify lists of keywords; the Provider provides software running in conjunction with the Search Engine, such that the Search Engine displays “links” to corresponding paid advertisements (“sponsored links”), that is, displays an advertisement on which the user can click to explore further, whenever such keywords appear in the user query. Such keyword-based advertising suffers from inherent revenue losses when advertisements containing the keywords are displayed but fail to attract the user's attention and, more significantly, by failing to display advertisements that are potentially attractive to users despite containing none of the presently entered keywords. Thus, it would be desirable to provide a means for identifying and displaying advertisements that are likely to be of interest to the user, and thus attract his or her attention, despite the fact that the advertisement does not correspond to any of the keywords entered per se.
According to the present invention such inherent revenue losses are reduced by identifying advertisements likely to be relevant in the ongoing search and appending the corresponding “complementary links” to the contractually mandated “sponsored links” in the search output. The invention takes advantage of the fact that, due to deficiencies inherent in keyword-based searching, consecutive user queries often have the same or overlapping underlying objectives despite different keywords; that is, the invention recognizes that often a user will not find what he or she is looking for in a particular search and will start over with different keywords. According to this aspect of the invention, a series of searches are collectively examined to identify and display complementary links to advertisements likely to be of interest to the user. For example, the user's selection of a result identified in the search output, for example, by clicking on an advertisement, indicates that the link may be relevant not only to the present search but also to searches preceding and following the present one in the search session. Accordingly, for example, the keywords from the preceding and subsequent searches can all be used to select the most relevant advertisements for display.
The invention is not limited to display of advertisements alone, although that is the context in which it will be described in detail. More specifically, similar techniques can be used according to the invention to improve Web searching per se; that is, the techniques described in detail below to identify and display advertisements that are likely to be of interest to a searcher can also be used to improve Web searching generally.
According to this invention, the interaction between the Search Engine and a user is modeled by a Finite State Probabilistic Automaton operated by the Provider and enabling the Provider to identify and display complementary links to advertisements. The Automaton has the capability of calculating the probability of relevance of possible advertisements from the histories of past searches conducted by multiple past users. Given the sequence of user inputs in the current session, the Automaton identifies and displays complementary links that are likely to satisfy user search objectives and thus maximize search engine revenues.